一、选择题（共70题，每题1分，满分70分。其中（1）—（55）题为中文题，（56）—（70）题为英文题）
下列各题A）、B）、C）、D）四个选项中，只有一个选项是正确的。请将正确选项填涂在答题卡相应位置上，答在试卷上不得分。
（1）下列描述中正确的是
A）断电后，ROM内保存的信息会丢失
B）断电后，RAM内保存的信息会丢失
C）ROM是辅助存储器，RAM是主存储器
D）ROM是主存储器，RAM是辅助存储器
答案：B
分析：RAM作主存。ROM不能，因为ROM只能读不能写。我们常说的主存就是只内存。
严格来说，作内存的是DRAM（动态随机存取存储器），动态刷新。
而SRAM这个并不常用。 所以断电后DRAM这个里的内容要丢失。
（2）操作数地址存放在寄存器中的寻址方式称为
A）相对寻址方式
B）变址寄存器寻址方式
C）寄存器寻址方式
D）寄存器间接寻址方式
答案：D
分析：A、操作数地址为程序计数器中的内容与位移量之和。 EA=(PC)+D
B、操作数地址为变址寄存器的内容与位移量之和。 EA=(R)变+D
C、操作数在寄存器中。
D、操作数的地址在寄存器中。
记住：凡是有间接的，都是以地址存储。
（3）指令译码器的输入信号来自于
A）整条指令 B）指令的操作码字段
C）指令的地址码字段 D）指令的操作数字段
答案：B
（4）对一棵二叉排序树进行某种遍历操作，可以得到该二叉树的所有结点按值有序排列的序列。该遍历操作是
A）前序遍历 B）后序遍历 C）中序遍历 D）按层次遍历
答案：C
分析：对二叉排序树中序遍历可以得到递增数的序列。
（5）若无向图采用邻接矩阵方法存储，则该邻接矩阵一定是
A）一般矩阵 B）对角矩阵 C）对称矩阵 D）稀疏矩阵
答案：C
分析：无向图邻接矩阵方法存储的矩阵是对称矩阵。
（6）已知散列函数为H(k)= k MOD 7，并且采用线性探测再散列方法处理冲突，依次将关键字15,10,45,20,27插入初始为空的散列表后，该散列表的状态是
答案：D
分析：15%7=1 10%7=3 45%7=3 20%7=6 遇到冲突填入下一个单元，到最末尾冲突填到第一个单元。
（7）根据（大顶）堆的定义，若对原始序列(26,5,77,1,61,11,59,15,48,19)进行堆排序，则第三趟排序结束时序列的状态是
A）(59,48,26,15,19,11,1,5,61,77) B）(5,48,26,15,19,11,1,59,61,77)
C）(1,48,26,15,19,11,5,59,61,77) D）(5,48,1,15,19,11,26,59,61,77)
答案：B
分析：首先应该弄明白堆排序的思想：
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点的值是最小(或最大)的。
设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。
大根堆的初始化
void HeapAdjust(S_TBL *h，int s，int m){/*r[s…m]中的记录关键码除r[s]外均满足堆的定义，本函数将对第s个结点为根的子树筛选，使其成为大顶堆*/
rc=h->r[s]；
for(j=2*s；j<=m；j=j*2) /* 沿关键码较大的子女结点向下筛选 */
{ if(jr[j].keyr[j+1].key)
j=j+1； /* 为关键码较大的元素下标*/
if(rc.keyr[j].key) break； /* rc应插入在位置s上*/
h->r[s]=h->r[j]；
s=j； /* 使s结点满足堆定义 */
}
h->r[s]=rc； /* 插入 */
}
然而，对堆排序采用如下算法：
void HeapSort(S_TBL *h)
{ for(i=h->length/2；i>0；i--) /* 将r[1..length]建成堆 */
HeapAdjust(h，i，h->length)；
for(i=h->length；i>1；i--)
{ h->r[1]<-->h->r[i]； /* 堆顶与堆低元素交换 */
HeapAdjust(h，1，i-1)； /*将r[1..i-1]重新调整为堆*/
}
}
第一趟排序如下： 77和5交换 （77排好——输出77）
第二趟排序如下： 1和61交换 （61排好——输出61）
第三趟排序如下： 5和59交换 （59排好——输出59）
因此，第三趟排序状态是5,48,26,15,19,11,1,59,61,77
（8）下面递归函数的功能是
typedef struct node{
datatype data;
struct node *link;
} *LinkList;
int FUN(LinkList list)
{
if(list==NULL)
return 0;
else
return 1+ FUN(list->link);
}
A）求一个链表的长度
B）在链表中删除一个结点
C）删除并释放一个链表占用的空间
D）逆转一个链表的链接方向
答案：A
分析：采用递归调用计算链表的长度。
（9）设解释I如下：个体域D={a,b}，F(x,y)为二元谓词，且F(a,a)=F(b,b)=1，F(a,b)=F(b,a)=0。在解释I下，下面公式中为假的是
答案：A
分析：首先要明白这两个的意思 F(a,a)=F(b,b)=1，F(a,b)=F(b,a)=0 对于二元关系F(x,y)，x对应的是其前域，y对应的是其后域。 这个F(a,
